# Floyd算法：权重矩阵n次Floyd乘方表示vi经过n个节点到的到达vj的权重

import numpy as np
from tools.Conversion import Conversion
from tools.Input import Input
from tools.Output import Output


class Floyd:
    __name = 'Floyd'

    @staticmethod
    def do_floyd():
        # g = Input.input_graph_matrix()  # 输入有向图
        g = Conversion.graph_arr_2_matrix(Input.get_graph2(), direction=True)  # 获取一个图（例3.4.2）
        print('输入的图为：')
        Output.print_graph_matrix(g)

        v_set = g[0]  # 图的点集
        s_set = g[1]  # 图的边集

        final_result = s_set  # floyd最短路径结果
        matrix_result = s_set  # floyd1次方为权重矩阵

        print('生成过程：')
        for i in range(len(v_set) - 2):  # 计算floyd(n-1)次方
            matrix_result = Floyd.matrix_multiplication(s_set, matrix_result)  # floyd乘方结果
            final_result = np.minimum(final_result, matrix_result)  # 路径长度取最小
            print('floyd({0})次方：'.format(i + 2))
            Output.print_graph_matrix([v_set, matrix_result])

        print('最短路长：')
        Output.print_graph_matrix([v_set, final_result])

    @staticmethod
    def matrix_multiplication(matrix1, matrix2):
        matrix1 = np.array(matrix1)
        matrix2 = np.array(matrix2)
        size = range(len(matrix1))
        matrix_result = []
        for i in size:  # 行
            line = []
            for j in size:  # 列
                d_ij = np.min(matrix1[i] + matrix2[:, j])  # 第i行 + 第j列，然后取最小值（i节点到j节点经过其他节点到达的最小值）
                line.append(d_ij)
            matrix_result.append(line)
        return matrix_result
